/* Zach Smith
 *
 * Project 1: Sort Algorithm Comparison
 *
 * MergeSort.java
 *
 * Original code found in "Data Abstraction & Problem Soving with Java"
 * 2005., Carrano, F., Prichard, J.; pg. 484
 *
 */

public class MergeSort 
{
    public static void MergeSort(int[] myArray, int first, int last) 
    {
        /***divides subarray in half***/
        if (first < last) 
        {
            int mid = (first + last)/2;
            MergeSort(myArray, first, mid);
            MergeSort(myArray, mid+1, last);
            
            Merge(myArray, first, mid, last);
        }
    }
    
    public static void Merge(int[] myArray, int first, int mid, int last) 
    {
        int max = myArray.length;
        
        int[] tempArray = new int[max];
        
        int leftFirst = first;
        int leftLast = mid;
        int rightFirst = mid+1;
        int rightLast = last;
        
        int index = leftFirst;
        
        /***compares the two subarrays***/
        while ((leftFirst <= leftLast) && (rightFirst <= rightLast)) 
        {
            if (myArray[leftFirst] < myArray[rightFirst])
            {
                tempArray[index] = myArray[leftFirst];
                leftFirst++;
            } else 
            {
                tempArray[index] = myArray[rightFirst];
                rightFirst++;
            }
            index++;
        }
        
        /***finishes left subarray if necessary***/
        while (leftFirst <= leftLast) 
        {
            tempArray[index] = myArray[leftFirst];
            leftFirst++;
            index++;
        }
        
        /***finishes right subarray if necessary***/
        while (rightFirst <= rightLast) 
        {
            tempArray[index] = myArray[rightFirst];
            rightFirst++;
            index++;
        }
        
        /***Loop to copy tempArray into myArray***/
        for (index = first; index <= last; ++index)
        {
            myArray[index] = tempArray[index];
        }
    }
}